This invention relates in general to computers capable of executing instructions out of order and, in particular, to a computer capable of tracking dependencies between out-of-order instructions that are used to access memory.
From the perspective of a programmer, instructions in a conventional processor are executed sequentially. When an instruction loads a new value into its destination register, that new value is immediately available for use by subsequent instructions. This is not true, however, for pipelined computer hardware because some results are not available for many clock cycles. Sequencing becomes more complicated in a superscalar processor, which has multiple execution pipelines running in parallel. But the hardware must behave as if each instruction were completed sequentially.
Each instruction depends on previous instructions which produced its operands, because it cannot begin execution until those operands become valid. These dependencies determine the order in which instructions can be executed. The actual execution order depends on the organization of the processor. In a typical pipelined processor, instructions are executed only in program order. The next sequential instruction may begin execution during the next cycle provided all its operands are valid. Otherwise, the pipeline stalls until the operands become valid. Because instructions execute in order, stalls usually delay all subsequent instructions. A sophisticated compiler can improve performance by re-arranging instructions to reduce the frequency of these stall cycles.
In an in-order superscalar processor, several consecutive instructions may begin execution simultaneously, if all their operands are valid, but the processor stalls at any instruction whose operands are still busy. In an out-of-order superscalar processor, each instruction is eligible to begin execution as soon as its operands become valid, independently of the original instruction sequence. In effect, the hardware re-arranges instructions to keep its execution units busy. This process is called "dynamic issuing."
Dynamic issue and execution of pipelined instructions creates a special need to monitor and resolve data dependencies between instructions. A newly-issued instruction is dependent on a previous instruction if, for example, the newly-issued instruction must use an output of the previous instruction as an operand. Such dependency inserts a restriction on the order of instruction execution.
Similarly, when out-of-order instructions are used in memory-access operations, the execution order of such instructions is restricted, at least in part, by memory dependency (i.e., two instructions accessing and altering the same memory location). Accordingly, there is a need for tracking the memory-dependency of memory-access instructions which may be executed out of order to maintain data integrity.